#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

int numTrees(int n) {
    vector<int> f(n + 1);
    f[0] = f[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++)
            f[i] += (f[j] * f[i - j - 1]);
    return f[n];
}

int maximalSquare(vector<vector<char>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    if (n == 0 || m == 0)
        return 0;

    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (matrix[i - 1][j - 1] == '1')
            {
                f[i][j] = min(f[i - 1][j], min(f[i - 1][j - 1], f[i][j - 1])) + 1;
                res = max(res, f[i][j]);
            }

    return res * res;
}

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size(), m = triangle[n - 1].size();
    vector<vector<int>> f(n + 1, vector<int>(m + 10));

    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j < triangle[i].size(); j++)
            f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
    return f[0][0];
}

int minDistance(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)   f[i][0] = i;
    for (int i = 1; i <= m; i++)   f[0][i] = i;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (s1[i - 1] == s2[j - 1])  f[i][j] = f[i - 1][j - 1];
            else
            {
                f[i][j] = f[i - 1][j - 1] + 1;
                f[i][j] = min(f[i][j], f[i][j - 1] + 1);
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
            }
    return f[n][m];
}